#include "heap.h"

Heap* HeapInit() {
    Heap* heap = MALLOC(Heap, 1);
    heap->_data = MALLOC(HPDataType, heap->_capacity = DEFAULT_CAPACITY);
    heap->_size = 0;
    return heap;
}
// 堆的销毁
void HeapDestory(Heap* heap) {
    free(heap->_data);
    free(heap);
}

int ParentIndex(int child) {
    return (child - 1) / 2;
}



void SiftUp(HPDataType* data, int child) {
    while (child > 0 && data[child] > data[ParentIndex(child)]) {
        SWAP(HPDataType, data[child], data[ParentIndex(child)]);
        child = ParentIndex(child);
    }
}

void SiftDown(HPDataType* data, int size, int parent) {
    int child = parent * 2 + 1;

    if (child + 1 < size && data[child + 1] > data[child]) {
        child++;
    }

    if (child < size && data[child] > data[parent]) {
        SWAP(HPDataType, data[child], data[parent]);
        SiftDown(data, size, child);
    }
}
// 堆的插入
void HeapPush(Heap* heap, HPDataType data) {
    if (heap->_size >= heap->_capacity) {
        heap->_data = REALLOC(heap->_data, HPDataType, heap->_capacity += heap->_capacity >> 1);
    }
    heap->_data[heap->_size++] = data;
    SiftUp(heap->_data, heap->_size - 1);
}
// 堆的删除
HPDataType HeapPop(Heap* heap) {
    assert(heap);
    if (HeapEmpty(heap)) {
        printf("HeapTop: Empty Heap!\n");
        return -1;
    }
    HPDataType ret = heap->_data[0];
    heap->_data[0] = heap->_data[heap->_size - 1];
    SiftDown(heap->_data, --heap->_size, 0);
    return ret;
}
// 取堆顶的数据
HPDataType HeapTop(Heap* heap) {
    assert(heap);
    if (HeapEmpty(heap)) {
        printf("HeapTop: Empty Heap!\n");
        return -1;
    }
    return heap->_data[0];
}
// 堆的数据个数
int HeapSize(Heap* heap) {
    assert(heap);
    return heap->_size;
}
// 堆的判空
bool HeapEmpty(Heap* heap) {
    assert(heap);
    return heap->_size == 0;
}